The present invention relates to a method and apparatus for handling information sent through a digital network and, more specifically, to a method and apparatus for servicing cells at a switch within such a network.
In Asynchronous Transfer Mode (ATM) or xe2x80x9ccell switchingxe2x80x9d, digital information is segmented into equal sized units called xe2x80x9ccellsxe2x80x9d that are transmitted from a source node to a destination node through a xe2x80x9cconnectionxe2x80x9d in a digital network. The digital network may be constructed of digital switches coupled together by digital communication links. At the destination node, the cells may be reassembled into user frames of data for presentation and/or further processing.
Within the digital network, each digital switch may be connected to many communication links. Furthermore, each communication link may carry many different connections simultaneously. Accordingly, cells belonging to each connection may need to be handled or serviced differently at each switch in order to meet overall network goals for supporting each connection.
Within each switch, a cell memory or buffer may be used for temporarily holding cells prior to transmission on a communication link. The cell memory may be arranged into logical queues. Several of such queues may be used for separating cells of different types of services and/or connections. For example, cells belonging to higher priority connections may be stored in queues that have a higher priority of service. In some cases, a separate queue may be assigned to each connection.
In such a digital switch, xe2x80x9cservicingxe2x80x9d of a queue may be accomplished by sending a cell of that queue out into the digital network on a communication link. In other words, the cell is removed from its associated queue and transmitted into the network. A service algorithm is employed to select a particular queue from among the number of logical queues of cells for service.
To date, however, there has not existed a means of fairly scheduling data traffic from multiple connections at a switch or other network node while at the same time providing for accurate explicit rate (ideally, per connection) feedback to upstream nodes or user end-systems.
It is an object of the invention to provide a method and apparatus for efficiently servicing cells at a node in a digital network.
It is a further object of the invention to provide a fair means of scheduling data traffic at a network node (e.g., a digital switch), with the option of providing accurate explicit rate feedback to upstream nodes or end-systems within the network.
In one embodiment, a service controller for a cell switched network may be configured to service a plurality of connection queues within the network according to a fair rate. The fair rate may be weighted for each of the connection queues. The service controller may be further configured to service the connection queues by moving cells from one or more of the connection queues to a class of service queue and the fair rate may be computed according to the length of the class of service queue and cell arrival and departure rate to and from the class of service queue.
In some embodiments, the service controller may be configured to service the connection queues at the computed fair rate, a guaranteed minimum rate or a rate which is a combination of the fair rate and the minimum rate.
In a further embodiment, cells in a digital network may be serviced by computing a fair rate for servicing the cells from a plurality of connection queues and moving the cells from the connection queues to a class of service queue according to the fair rate. Each of the connection queues may have an associated weight and each connection queue may be serviced at a rate according to the fair rate and the weight associated with the connection queue being serviced. The fair rate may be computed by computing a target rate for servicing the connection queues, computing an observed arrival rate for cells arriving at the class of service queue, and computing the fair rate according to a ratio of the target rate to their observed arrival rate. The target rate may be approximated according to an amount of available bandwidth for the class of service queue and the number of cells serviced from the class of service queue in a period of time.
In some embodiments, the fair rate may be periodically recomputed or recomputed once a predetermined number of cells have been received or have departed (e.g., based or a cell count instead of a time period). Further, the fair rate may be multiplied by a fixed constant (e.g., doubled) at each recomputation if a class of service queue empties during the period preceding the recomputation.
In yet further embodiments, cells within a digital network may be stamped with a fair rate to provide explicit rate control within said network. The fair rate used for explicit rate control may be the same fair rate computed for servicing cells from connection queues at a node within the digital network.
In still further embodiments, the present invention provides for caching service decisions for a number of a plurality of queues of cells or packets in a network; and the servicing those service decisions. Servicing the service decisions may include replacing (e.g., by overwriting) old service decisions if new service requests for any of the queues are received, otherwise the old service decisions may be reserviced.
The new service requests may be generated for each of the queues according to a fair rate or respective weighted fair rates. The fair rate and/or the weighted fair rates may be bounded by at least a minimum rate.
These and other features and advantages provided by the present invention will be apparent from the detailed description which follows and upon references to the accompanying figures described therein.